#include "vetor.h"


/* counting sort adaptado para radix sort
*  ordena vetor de acordo com o digito 
*  representado por exp
*  @entradas:
*    L: vetor
*	 N: tamanho do vetor
*    exp: potencia de 10 representada pelo digito
*/
void counting_sort(int* L, int N, int exp){
	int C[10] = { 0 };

	for (int i = 0; i < N; i++)
		C[(L[i] / exp) % 10]++;

	for (int i = 1; i < 10; i++)
		C[i] += C[i - 1];

	int *ret = new int[N];
	for (int i = N - 1; i >= 0; i--){
		C[(L[i] / exp) % 10]--;
		ret[C[(L[i] / exp) % 10]] = L[i];
	}

	for (int i = 0; i < N; i++)
		L[i] = ret[i];
}

/* ordenacao radix sort
*  @entradas:
*    L: vetor
*	 N: tamanho do vetor
*/
void radix_sort(int* L, int N){
	int max = max_value(L, N);
	for (int exp = 1; max / exp > 0; exp *= 10)
		counting_sort(L, N, exp);
}

